import java.util.Arrays;
import java.util.Stack;

/**
 * @program: LeetCode
 * @description: LeetCode : 503. 下一个更大元素 II
 * @author: WXY
 * @create: 2023-02-03 14:56
 * @Version 1.0
 **/
public class Num503_nextGreaterElements {
    public static int[] nextGreaterElements1(int[] nums) {
        int[] arr = new int[nums.length * 2];
        int index = 0;
        for (int i = 0; index < arr.length; i++) {
            if (i > nums.length - 1) {
                i = i - nums.length;
            }
            arr[index++] = nums[i];
        }
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[arr.length];
        Arrays.fill(ans, -1);
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                ans[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        return Arrays.copyOfRange(ans,0,nums.length);
    }



    public static int[] nextGreaterElements(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = -1;
        }
        if (nums.length == 0) return ans;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length * 2; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % nums.length]) {
                int index = stack.pop();
                ans[index] = nums[i % nums.length];
            }
            stack.push(i % nums.length);
        }
        return ans;
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 1};
        for (int i : nextGreaterElements(arr)) {
            System.out.print(i + " ");
        }

    }
}
